#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    static int triangleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int max = nums.size()-1;
        int ret = 0;

        while(max >= 2)
        {
            int left = 0;
            int right = max-1;
            while(left <right)
            {
                if(nums[left] + nums[right] > nums[max])
                {
                    ret += (right-left);
                    right--;
                }
                else
                {
                    left++;
                }
            }
            max--;
        }
        return ret;
    }
};
